using System;
using System.Collections.Generic;

using Atomic.Libraries;

namespace Atomic.Structures.Symmetries
{
	[Serializable]
	public class StructureGeneratorNaive
	{
		public StructureGeneratorNaive(Structure lattice)
		{
			List<PlaceholderAtom> placeholders = new List<PlaceholderAtom>();
			long n = 1;

			foreach (Site site in lattice.Sites)
			{
				PlaceholderAtom placeholder = site.Atom as PlaceholderAtom;

				if (placeholder != null)
				{
					placeholders.Add(placeholder);
					n *= placeholder.Atoms.Count;
				}
			}

			Lattice = lattice;
			Placeholders = new ReadOnlyList<PlaceholderAtom>(placeholders);
			Count = (int)n;
			LongCount = n;
		}

		public IEnumerable<Structure> Generate()
		{
			// Iterate through combinations.
			for (int i = 0; i < Count; i++)
			{
				List<Atom> atoms = new List<Atom>();

				long k = i;
				foreach (PlaceholderAtom placeholder in Placeholders)
				{
					atoms.Add(placeholder.Atoms[(int)(k % placeholder.Atoms.Count)]);
					k /= placeholder.Atoms.Count;
				}

				yield return Lattice.FillPlaceholders(atoms);
			}
		}

		/// <summary>
		/// Generate all combinations with this many placeholders being filled with the specified atom. The remaining placeholders are left unchanged.
		/// </summary>
		public IEnumerable<Structure> GeneratePartial(Atom atom, int count)
		{
			if (count < 0)
			{
				throw new ArgumentException();
			}

			// Count total number of placeholders containing this atom.
			int n = 0;
			foreach (PlaceholderAtom placeholder in Placeholders)
			{
				if (placeholder.Atoms.Contains(atom))
				{
					n++;
				}
			}

			if (count > n)
			{
				throw new ArgumentException("More atoms specified than available placeholders.");
			}

			int k = count;
			int[] item = null;
			while (NextCombination(ref item, k, n))
			{
				int l = 0;
				List<int> item0 = new List<int>(item);

				List<Atom> atoms = new List<Atom>();
				foreach (PlaceholderAtom placeholder in Placeholders)
				{
					if (placeholder.Atoms.Contains(atom))
					{
						// Implement a more efficient lookup method!
						if (item0.Contains(l))
						{
							// This placeholder was selected. Replace by specified atom.
							atoms.Add(atom);
						}
						else
						{
							// Otherwise just remove the atom from the placeholder.
							atoms.Add(placeholder.Remove(atom));
						}

						l++;
					}
					else
					{
						// Leave unchanged if this placeholder doesn't contain the specified atom.
						atoms.Add(placeholder);
					}
				}

				yield return Lattice.FillPlaceholders(atoms);
			}
		}

		private bool NextCombination(ref int[] item, int k, int n)
		{
			if (item == null)
			{
				// First combination.
				item = new int[k];
				for (int i = 0; i < k; i++)
				{
					item[i] = i;
				}

				return true;
			}

			// http://stackoverflow.com/a/5077264
		    for (int i = 0; i < k; i++)
			{
				if (item[k - i - 1] < n - i - 1)
				{
					item[k - i - 1]++;
					for (int j = k - i; j < k; j++)
					{
						item[j] = item[j - 1] + 1;
					}

					return true;
				}
			}

			// No more combinations.
			return false;
		}

		/// <summary>
		/// Fills placeholders with the corresponding atoms in all possible ways, not considering symmetry. The may be faster than trying to figure out symmetrically district combinations.
		/// </summary>
		public static IEnumerable<Structure> Generate(Structure lattice)
		{
			return new StructureGeneratorNaive(lattice).Generate();
		}

		/// <summary>
		/// Fills placeholders a number of placeholder with the specified atom in all possible ways, not considering symmetry. The remaining placeholders are left unchanged.
		/// </summary>
		public static IEnumerable<Structure> GeneratePartial(Structure lattice, Atom atom, int count)
		{
			return new StructureGeneratorNaive(lattice).GeneratePartial(atom, count);
		}

		public Structure Lattice
		{
			get;
			private set;
		}

		public ReadOnlyList<PlaceholderAtom> Placeholders
		{
			get;
			private set;
		}

		public int Count
		{
			get;
			private set;
		}

		public long LongCount
		{
			get;
			private set;
		}

		/*private class Combination
		{
			private bool[] current;

			public Combination(int n, int k)
			{
				current = new bool[n];
				for (int i = 0; i < n; i++)
				{
					current[i] = i < k;
				}
			}

			public bool[] Next()
			{

			}
		}*/
	}
}
